<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>PyMOTW: heapq &mdash; PyMOTW Document v1.6 documentation</title>
    <link rel="stylesheet" href="../_static/mytest.css" type="text/css" />
    <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../',
        VERSION:     '1.6',
        COLLAPSE_MODINDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="../_static/jquery.js"></script>
    <script type="text/javascript" src="../_static/doctools.js"></script>
    
    <!-- comment utility -->
    <link rel="stylesheet" href="../_static/comment.css" type="text/css" />
    <script type="text/javascript" src="../_static/md5.js"></script>
    <script type="text/javascript" src="../_static/comment.js"></script>
    <!-- end -->
    <link rel="author" title="About these documents" href="../about.html" />
    <link rel="copyright" title="Copyright" href="../copyright.html" />
    <link rel="top" title="PyMOTW Document v1.6 documentation" href="../index.html" />
    <link rel="prev" title="PyMOTW: unittest" href="unittest.html" /> 
  </head>
  <body>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="unittest.html" title="PyMOTW: unittest"
             accesskey="P">previous</a> |</li>
        <li><a href="../index.html">PyMOTW Document v1.6 documentation</a> &raquo;</li> 
      </ul>
    </div> 
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="../index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference external" href="">PyMOTW: heapq</a><ul>
<li><a class="reference external" href="#id1">描述</a></li>
<li><a class="reference external" href="#id2">示例数据</a></li>
<li><a class="reference external" href="#id3">创建一个堆</a></li>
<li><a class="reference external" href="#id4">访问堆</a></li>
<li><a class="reference external" href="#id5">数据极值</a></li>
<li><a class="reference external" href="#id6">参考</a></li>
</ul>
</li>
</ul>

            <h4>Previous topic</h4>
            <p class="topless"><a href="unittest.html"
                                  title="previous chapter">PyMOTW: unittest</a></p>
            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../_sources/documents/heapq.txt"
                     rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <form class="search" action="../search.html" method="get">
                <input type="text" name="q" size="18" />
                <input type="submit" value="Go" />
                <input type="hidden" name="check_keywords" value="yes" />
                <input type="hidden" name="area" value="default" />
              </form>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div> 

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="pymotw-heapq">
<h1>PyMOTW: heapq<a class="headerlink" href="#pymotw-heapq" title="Permalink to this headline">¶</a></h1>
<ul class="simple">
<li>模块： heapq</li>
<li>目的： 就地堆排序算法</li>
<li>python版本：New in 2.3 with additions in 2.5 2.3+, 2.5中有所增加</li>
</ul>
<p>heapq实现了适用于Python列表的小顶堆排序算法.</p>
<div class="section" id="id1">
<h2>描述<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h2>
<p>堆是一种树型数据结构, 其父子节点间具有顺序关系. 二进制堆可以使用一个列表或数组来表示, 其中元素N的孩子所在位置为2*N+1 和 2*N+2(以0开始计算位置). 这种特征让就地重排成为可能, 这样在增加或删除元素时就不需要重新分配内存空间.</p>
<p>大顶堆确保每个父元素都大于或等于他的任一个孩子元素. 而小顶堆则需要每个父元素都要小于或等于他的任一个孩子元素. Python的heapq模块实现的是小顶堆.</p>
</div>
<div class="section" id="id2">
<h2>示例数据<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h2>
<p>本文的例子中使用的是如下的示例数据:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="n">data</span> <span class="o">=</span> <span class="p">[</span><span class="mf">19</span><span class="p">,</span> <span class="mf">9</span><span class="p">,</span> <span class="mf">4</span><span class="p">,</span> <span class="mf">10</span><span class="p">,</span> <span class="mf">11</span><span class="p">,</span> <span class="mf">8</span><span class="p">,</span> <span class="mf">2</span><span class="p">]</span>
</pre></div>
</div>
</div>
<div class="section" id="id3">
<h2>创建一个堆<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h2>
<p>有两个基本的堆创建方式, 分别是heappush()和heapify().</p>
<p>使用heappush(), 堆中元素排序顺序是随着新元素的不断增加而不断更新的.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">heapq_showtree</span> <span class="kn">import</span> <span class="n">show_tree</span>
<span class="kn">from</span> <span class="nn">heapq_heapdata</span> <span class="kn">import</span> <span class="n">data</span>

<span class="n">heap</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">print</span> <span class="s">&#39;random :&#39;</span><span class="p">,</span> <span class="n">data</span>
<span class="k">print</span>

<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="n">data</span><span class="p">:</span>
    <span class="k">print</span> <span class="s">&#39;add </span><span class="si">%3d</span><span class="s">:&#39;</span> <span class="o">%</span> <span class="n">n</span>
    <span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">heap</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span>
    <span class="n">show_tree</span><span class="p">(</span><span class="n">heap</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-python"><pre>$ python heapq_heappush.py
random : [19, 9, 4, 10, 11, 8, 2]

add  19:

                 19
------------------------------------

add   9:

                 9
        19
------------------------------------

add   4:

                 4
        19                9
------------------------------------

add  10:
                 4
        10                9
    19
------------------------------------

add  11:

                 4
        10                9
    19       11
------------------------------------

add   8:

                 4
        10                8
   19       11       9
------------------------------------

add   2:

                 2
        10                4
    19       11       9        8
------------------------------------</pre>
</div>
<p>如果数据已经在内存中了, 使用heapify()进行就地排序会更有效.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">heapq_showtree</span> <span class="kn">import</span> <span class="n">show_tree</span>
<span class="kn">from</span> <span class="nn">heapq_heapdata</span> <span class="kn">import</span> <span class="n">data</span>

<span class="k">print</span> <span class="s">&#39;random :&#39;</span><span class="p">,</span> <span class="n">data</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;heapified :&#39;</span>
<span class="n">show_tree</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-python"><pre>$ python heapq_heapify.py
random : [19, 9, 4, 10, 11, 8, 2]
heapified :

                 2
        9                 4
    10       11       8        19
------------------------------------</pre>
</div>
</div>
<div class="section" id="id4">
<h2>访问堆<a class="headerlink" href="#id4" title="Permalink to this headline">¶</a></h2>
<p>成功建立堆之后, 可以使用heappop()删除堆中最小的元素. 下面的例子改编自标准库文档中的例子, heapify()和heappop()用于对一个列表进行排序.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">heapq_showtree</span> <span class="kn">import</span> <span class="n">show_tree</span>
<span class="kn">from</span> <span class="nn">heapq_heapdata</span> <span class="kn">import</span> <span class="n">data</span>

<span class="k">print</span> <span class="s">&#39;random :&#39;</span><span class="p">,</span> <span class="n">data</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;heapified :&#39;</span>
<span class="n">show_tree</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
<span class="k">print</span>

<span class="n">inorder</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">while</span> <span class="n">data</span><span class="p">:</span>
    <span class="n">smallest</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
    <span class="k">print</span> <span class="s">&#39;pop </span><span class="si">%3d</span><span class="s">:&#39;</span> <span class="o">%</span> <span class="n">smallest</span>
    <span class="n">show_tree</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
    <span class="n">inorder</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">smallest</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;inorder :&#39;</span><span class="p">,</span> <span class="n">inorder</span>
</pre></div>
</div>
<div class="highlight-python"><pre>$ python heapq_heappop.py
 random    : [19, 9, 4, 10, 11, 8, 2]
 heapified :

                  2
         9                 4
     10       11       8        19
 ------------------------------------


 pop      2:

                  4
         9                 8
     10       11       19
 ------------------------------------

 pop      4:

                  8
         9                 19
     10       11
 ------------------------------------

 pop      8:

                  9
         10                19
     11
 ------------------------------------

 pop      9:

                  10
         11                19
 ------------------------------------

 pop     10:

                  11
         19
 ------------------------------------

 pop     11:

                  19
 ------------------------------------

 pop     19:

 ------------------------------------

 inorder   : [2, 4, 8, 9, 10, 11, 19]</pre>
</div>
<p>使用heapreplace()可以删除现有元素和用新的值替换已存元素.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">heapq_showtree</span> <span class="kn">import</span> <span class="n">show_tree</span>
<span class="kn">from</span> <span class="nn">heapq_heapdata</span> <span class="kn">import</span> <span class="n">data</span>

<span class="n">heapq</span><span class="o">.</span><span class="n">heapify</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;start:&#39;</span>
<span class="n">show_tree</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>

<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="p">[</span><span class="mf">0</span><span class="p">,</span> <span class="mf">7</span><span class="p">,</span> <span class="mf">13</span><span class="p">,</span> <span class="mf">9</span><span class="p">,</span> <span class="mf">5</span><span class="p">]:</span>
    <span class="n">smallest</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heapreplace</span><span class="p">(</span><span class="n">data</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span>
    <span class="k">print</span> <span class="s">&#39;replace </span><span class="si">%2d</span><span class="s"> with </span><span class="si">%2d</span><span class="s">:&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="n">smallest</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span>
    <span class="n">show_tree</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
</pre></div>
</div>
<p>这个功能让你维持了一个固定大小的堆, 这在具有优先级任务队列中是很用的.</p>
<div class="highlight-python"><pre>$ python heapq_heapreplace.py
start:

                 2
        9                 4
    10       11       8        19
------------------------------------

replace  2 with  0:

                 0
        9                 4
    10       11       8        19
------------------------------------

replace  0 with  7:

                 4
        9                 7
    10       11       8        19
------------------------------------

replace  4 with 13:

                 7
        9                 8
    10       11       13       19
------------------------------------

replace  7 with  9:

                 8
        9                 9
    10       11       13       19
------------------------------------

replace  8 with  5:

                 5
        9                 9
    10       11       13       19
------------------------------------</pre>
</div>
</div>
<div class="section" id="id5">
<h2>数据极值<a class="headerlink" href="#id5" title="Permalink to this headline">¶</a></h2>
<p>heapq也包含了2个用于检查迭代对象中最大或最小的值范围. 使用nlargest()和nsmallest()可以获得相对最小或最大的n个数, n一般大于1, 但在有些情况下不能获得正确的值.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">heapq</span>
<span class="kn">from</span> <span class="nn">heapq_heapdata</span> <span class="kn">import</span> <span class="n">data</span>

<span class="k">print</span> <span class="s">&#39;all :&#39;</span><span class="p">,</span> <span class="n">data</span>
<span class="k">print</span> <span class="s">&#39;3 largest :&#39;</span><span class="p">,</span> <span class="n">heapq</span><span class="o">.</span><span class="n">nlargest</span><span class="p">(</span><span class="mf">3</span><span class="p">,</span> <span class="n">data</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;from sort :&#39;</span><span class="p">,</span> <span class="nb">list</span><span class="p">(</span><span class="n">reversed</span><span class="p">(</span><span class="n">sorted</span><span class="p">(</span><span class="n">data</span><span class="p">)[</span><span class="o">-</span><span class="mf">3</span><span class="p">:]))</span>
<span class="k">print</span> <span class="s">&#39;3 smallest:&#39;</span><span class="p">,</span> <span class="n">heapq</span><span class="o">.</span><span class="n">nsmallest</span><span class="p">(</span><span class="mf">3</span><span class="p">,</span> <span class="n">data</span><span class="p">)</span>
<span class="k">print</span> <span class="s">&#39;from sort :&#39;</span><span class="p">,</span> <span class="n">sorted</span><span class="p">(</span><span class="n">data</span><span class="p">)[:</span><span class="mf">3</span><span class="p">]</span>
</pre></div>
</div>
<div class="highlight-python"><pre>$ python heapq_extremes.py
all : [19, 9, 4, 10, 11, 8, 2]
3 largest : [19, 11, 10]
from sort : [19, 11, 10]
3 smallest: [2, 4, 8]
from sort : [2, 4, 8]</pre>
</div>
</div>
<div class="section" id="id6">
<h2>参考<a class="headerlink" href="#id6" title="Permalink to this headline">¶</a></h2>
<ul class="simple">
<li><a class="reference external" href="http://docs.python.org/lib/node92.html">heapq Theory</a></li>
<li><a class="reference external" href="http://en.wikipedia.org/wiki/Heap_%28data_structure%29">WikiPedia - Heap Data Structure</a></li>
</ul>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="unittest.html" title="PyMOTW: unittest"
             >previous</a> |</li>
        <li><a href="../index.html">PyMOTW Document v1.6 documentation</a> &raquo;</li> 
      </ul>
    </div>
    <div class="footer">
      &copy; <a href="../copyright.html">Copyright</a> 2009, vbarter &amp; liz.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.3.
    </div>
  </body>
</html>